package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         133,
		Discription: "加油站",
		Level:       2,
		Labels: map[string]int{
			"贪心": 1,
		},
	})
}

// CanCompleteCircuit 核心思想：若从i出发，在j时无法再往前了，说明：从i,i+1,..,j-1的任意一点出发，最多到达j（因为从i出发时，从i+1,...,j-1带着>=0的gas余量出发都会卡在j，不带余量肯定也会卡在j）
// 所以[i,j]区间内的节点都不能作为起始节点，直接看到j+1
//  @param gas
//  @param cost
//  @return int
func CanCompleteCircuit(gas []int, cost []int) int {
	n := len(gas)
	start := 0
	for start < n {
		gasLeft := 0
		count := 0
		i := start
		for gasLeft+gas[i]-cost[i] >= 0 {
			gasLeft += gas[i] - cost[i]
			count++
			if count == n {
				return start
			}

			if i == n-1 {
				//超圈
				i = 0
			} else {
				i++
			}
		}

		//避免无限循环
		if i < start {
			break
		}
		start = i + 1
	}

	return -1
}
